package com.gxc.recursion;

import java.util.Stack;

/**
 * 栈逆序
 * 给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数
 */
public class StackReverseRrder {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(2);
        stack.push(1);
        printStack(stack);

        stack.push(3);
        stack.push(2);
        stack.push(1);
        reverse(stack);
        printStack(stack);
    }

    private static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) return;
        int last = removeLastElement(stack);
        reverse(stack);
        stack.push(last);
    }

    /**
     * 返回栈中最后一个元素
     * 1,2,3
     * 返回3后
     * 栈内还有1,2
     * @param stack
     * @return
     */
    private static int removeLastElement(Stack<Integer> stack) {
        //如果栈为最后一个元素则返回
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        }
        int temp = removeLastElement(stack);
        //如果栈不是最后一个元素，则压回栈内
        stack.push(result);
        return temp;
    }

    private static void printStack(Stack<Integer> stack) {
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

}
